/*
 * @lc app=leetcode.cn id=19 lang=cpp
 *
 * [19] 删除链表的倒数第N个节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n)
  {
    if (head == NULL) return NULL;
    // 1.在有头结点可能删除的情况，创建虚拟头结点，减少讨论头结点被删的情况
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;

    // first向后走n步
    ListNode* first = dummy;
    ListNode* second = dummy;
    // first向后走n步()
    while (n--) first = first->next;
    // first,second同时向后走，当first走到尾部时终止(此时second指向倒数n+1个节点)
    while (first->next)
    {
      first = first->next;
      second = second->next;
    }

    // 删除倒数第n节点、或者叫略去
    second->next = second->next->next;

    return dummy->next;  // 返回虚拟头结点next，不能直接返回头结点，有可能头结点被删除
  }
};
// @lc code=end
